home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / DJLSR106.ARJ / BITSTRIN.CC < prev    next >
C/C++ Source or Header  |  1992-03-30  |  49KB  |  2,065 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitString class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation "BitString.h"
  24. #endif
  25. #include <BitString.h>
  26. #include <std.h>
  27. #include <values.h>
  28. #include <_Obstack.h>
  29. #include <AllocRing.h>
  30. #include <new.h>
  31. #include <builtin.h>
  32.  
  33. void BitString::error(const char* msg) const
  34. {
  35.   (*lib_error_handler)("BitString", msg);
  36. }
  37.  
  38. //  globals
  39.  
  40. BitStrRep    _nilBitStrRep = {  0, 1, {0} };
  41.  
  42. BitString _nil_BitString;
  43.  
  44. #define MINBitStrRep_SIZE  8
  45. #define MAXBitStrRep_SIZE  ((1 << (SHORTBITS - 1)) - 1)
  46.  
  47. #ifndef MALLOC_MIN_OVERHEAD
  48. #define MALLOC_MIN_OVERHEAD    4
  49. #endif
  50.  
  51. #define ONES  ((unsigned short)(~0L))
  52. #define MAXBIT  (1 << (BITSTRBITS - 1))
  53.  
  54. /*
  55.  *  bit manipulation utilities
  56. */
  57.  
  58. // break things up into .s indices and positions
  59.  
  60. inline static int BitStr_len(int l)
  61. {
  62.   return (unsigned)(l) / BITSTRBITS + 1;
  63. }
  64.  
  65.  
  66. // mask out low bits
  67.  
  68. static inline unsigned short lmask(int p)
  69. {
  70.   if (p <= 0)
  71.     return ONES;
  72.   else
  73.     return ONES << p;
  74. }
  75.  
  76. // mask out high bits
  77.  
  78. static inline unsigned short rmask(int p)
  79. {
  80.   int s = BITSTRBITS - 1 - p;
  81.   if (s <= 0)
  82.     return ONES;
  83.   else
  84.     return ONES >> s;
  85. }
  86.  
  87.  
  88. // mask out unused bits in last word of rep
  89.  
  90. inline static void check_last(BitStrRep* r)
  91. {
  92.   r->s[r->len / BITSTRBITS] &= ONES >> (BITSTRBITS - (r->len & (BITSTRBITS - 1)));
  93. }
  94.  
  95. // merge bits from next word
  96.  
  97. static inline unsigned short borrow_hi(const unsigned short a[], int ind, 
  98.                                       int maxind, int p)
  99. {
  100.   if (ind < maxind)
  101.     return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p));
  102.   else
  103.     return (a[ind] >> p);
  104. }
  105.  
  106. // merge bits from prev word
  107.  
  108. static inline unsigned short borrow_lo(const unsigned short a[], int ind, 
  109.                                       int minind, int p)
  110. {
  111.   if (ind > minind)
  112.     return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1));
  113.   else
  114.     return (a[ind] << (BITSTRBITS - 1 - p));
  115. }
  116.  
  117. // same with bounds check (for masks shorter than patterns)
  118.  
  119. static inline unsigned short safe_borrow_hi(const unsigned short a[], int ind, 
  120.                                            int maxind, int p)
  121. {
  122.   if (ind > maxind)
  123.     return 0;
  124.   else if (ind == maxind)
  125.     return(a[ind] >> p);
  126.   else
  127.     return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p));
  128. }
  129.  
  130.  
  131. static inline unsigned short safe_borrow_lo(const unsigned short a[], int ind, 
  132.                                             int minind, int p)
  133. {
  134.   if (ind < minind)
  135.     return 0;
  136.   else if (ind == minind)
  137.     return (a[ind] << (BITSTRBITS - 1 - p));
  138.   else
  139.     return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1));
  140. }
  141.  
  142. // copy bits from a word boundary
  143.  
  144. static inline void bit_copy(const unsigned short* ss, unsigned short* ds, 
  145.                             int nbits)
  146. {
  147.   if (ss != ds)
  148.   {
  149.     int n = (unsigned)(nbits) / BITSTRBITS;
  150.     if (n > 0) bcopy((void*)ss, (void*)ds, n * sizeof(short));
  151.     unsigned short m = ONES << (nbits & (BITSTRBITS - 1));
  152.     ds[n] = (ss[n] & ~m) | (ds[n] & m);
  153.   }
  154. }
  155.  
  156. // clear bits from a word boundary
  157.  
  158. static inline void bit_clear(unsigned short* ds, int nbits)
  159. {
  160.   int n = (unsigned)(nbits) / BITSTRBITS;
  161.   if (n > 0) bzero((void*)ds, n * sizeof(short));
  162.   ds[n] &= ONES << (nbits & (BITSTRBITS - 1));
  163. }
  164.  
  165.   
  166.  
  167. // Copy ss from starts to fences-1 into ds starting at startd.
  168. // This will work even if ss & ds overlap.
  169. // The g++ optimizer does very good things with the messy shift expressions!
  170.  
  171. static void bit_transfer(const unsigned short* ss, int starts, int fences,
  172.                          unsigned short* ds, int startd)
  173. {
  174.   if (starts >= fences || ss == 0 || (ss == ds && starts == startd))
  175.     return;
  176.  
  177.   int sind = BitStr_index(starts);
  178.   int spos = BitStr_pos(starts);
  179.   int dind = BitStr_index(startd);
  180.   int dpos = BitStr_pos(startd);
  181.  
  182.   if (spos == 0 && dpos == 0)
  183.   {
  184.     bit_copy(&ss[sind], &ds[dind], fences - starts);
  185.     return;
  186.   }
  187.  
  188.   int ends = fences - 1;
  189.   int endsind = BitStr_index(ends);
  190.   int endspos = BitStr_pos(ends);
  191.   int endd = startd + (ends - starts);
  192.   int enddind = BitStr_index(endd);
  193.   int enddpos = BitStr_pos(endd);
  194.  
  195.   if (dind == enddind)
  196.   {
  197.     if (sind == endsind)
  198.       ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | 
  199.                               (ONES << (enddpos + 1)))) | 
  200.                                 (((ss[sind] >> spos) << dpos) & 
  201.                                  ~((ONES >> (BITSTRBITS - dpos)) | 
  202.                                    (ONES << (enddpos + 1))));
  203.     else
  204.       ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | 
  205.                               (ONES << (enddpos + 1)))) | 
  206.                                 ((((ss[sind] >> spos) | 
  207.                                    (ss[sind+1] << (BITSTRBITS - spos))) 
  208.                                   << dpos) & 
  209.                                  ~((ONES >> (BITSTRBITS - dpos)) | 
  210.                                    (ONES << (enddpos + 1))));
  211.     return;
  212.   }
  213.   else if (sind == endsind)
  214.   {
  215.     unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | 
  216.         (((ss[sind] << (BITSTRBITS - 1 - endspos)) >> 
  217.           (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
  218.     ds[dind] = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) |
  219.         (((ss[sind] >> spos) << dpos) & ~(ONES >> (BITSTRBITS - dpos)));
  220.     ds[enddind] = saveend;
  221.     return;
  222.   }
  223.  
  224.   unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | 
  225.     ((((ss[endsind] << (BITSTRBITS - 1 - endspos)) |
  226.        (ss[endsind-1] >> (endspos + 1))) >> 
  227.       (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
  228.   unsigned short savestart = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) |
  229.     ((((ss[sind] >> spos) | (ss[sind+1] << (BITSTRBITS - spos))) << dpos) 
  230.      & ~(ONES >> (BITSTRBITS - dpos)));
  231.  
  232.  
  233.   if (ds != ss || startd < starts)
  234.   {
  235.     int pos = spos - dpos;
  236.     if (pos < 0)
  237.       pos += BITSTRBITS;
  238.     else
  239.       ++sind;
  240.     
  241.     for (;;)                    // lag by one in case of overlaps
  242.     {
  243.       if (dind == enddind - 1)
  244.       {
  245.         ds[dind] = savestart;
  246.         ds[enddind] = saveend;
  247.         return;
  248.       }
  249.       else
  250.       {
  251.         unsigned short tmp = ss[sind] >> pos;
  252.         if (++sind <= endsind) tmp |= ss[sind] << (BITSTRBITS - pos);
  253.         ds[dind++] = savestart;
  254.         savestart = tmp;
  255.       }
  256.     }
  257.   }
  258.   else
  259.   {
  260.     int pos = endspos - enddpos;
  261.     if (pos <= 0)
  262.     {
  263.       pos += BITSTRBITS;
  264.       --endsind;
  265.     }
  266.     for (;;)
  267.     {
  268.       if (enddind == dind + 1)
  269.       {
  270.         ds[enddind] = saveend;
  271.         ds[dind] = savestart;
  272.         return;
  273.       }
  274.       else
  275.       {
  276.         unsigned short tmp = ss[endsind] << (BITSTRBITS - pos);
  277.         if (--endsind >= sind) tmp |= ss[endsind] >> pos;
  278.         ds[enddind--] = saveend;
  279.         saveend = tmp;
  280.       }
  281.     }
  282.   }
  283. }
  284.   
  285. // allocate a new rep; pad to near a power of two
  286.  
  287. inline static BitStrRep* BSnew(int newlen)
  288. {
  289.   unsigned int siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(short) 
  290.     + MALLOC_MIN_OVERHEAD;
  291.   unsigned int allocsiz = MINBitStrRep_SIZE;;
  292.   while (allocsiz < siz) allocsiz <<= 1;
  293.   allocsiz -= MALLOC_MIN_OVERHEAD;
  294.   if (allocsiz >= MAXBitStrRep_SIZE * sizeof(short))
  295.     (*lib_error_handler)("BitString", "Requested length out of range");
  296.     
  297.   BitStrRep* rep = (BitStrRep *) new char[allocsiz];
  298.   bzero(rep, allocsiz);
  299.   rep->sz = (allocsiz - sizeof(BitStrRep) + sizeof(short)) / sizeof(short);
  300.   return rep;
  301. }
  302.  
  303. BitStrRep* BStr_alloc(BitStrRep* old, const unsigned short* src,
  304.                       int startpos, int endp, int newlen)
  305. {
  306.   if (old == &_nilBitStrRep) old = 0; 
  307.   if (newlen < 0) newlen = 0;
  308.   int news = BitStr_len(newlen);
  309.   BitStrRep* rep;
  310.   if (old == 0 || news > old->sz)
  311.     rep = BSnew(newlen);
  312.   else
  313.     rep = old;
  314.   rep->len = newlen;
  315.  
  316.   if (src != 0 && endp > 0 && (src != rep->s || startpos > 0)) 
  317.     bit_transfer(src, startpos, endp, rep->s, 0);
  318.  
  319.   check_last(rep);
  320.  
  321.   if (old != rep && old != 0) delete old;
  322.  
  323.   return rep;
  324. }
  325.  
  326. BitStrRep* BStr_resize(BitStrRep* old, int newlen)
  327. {
  328.   BitStrRep* rep;
  329.   if (newlen < 0) newlen = 0;
  330.   int news = BitStr_len(newlen);
  331.   if (old == 0 || old == &_nilBitStrRep)
  332.   {
  333.     rep = BSnew(newlen);
  334.   }
  335.   else if (news > old->sz)
  336.   {
  337.     rep = BSnew(newlen);
  338.     bcopy(old->s, rep->s, BitStr_len(old->len) * sizeof(short));
  339.     delete old;
  340.   }
  341.   else
  342.     rep = old;
  343.  
  344.   rep->len = newlen;
  345.   check_last(rep);
  346.   return rep;
  347. }
  348.  
  349. BitStrRep* BStr_copy(BitStrRep* old, const BitStrRep* src)
  350. {
  351.   BitStrRep* rep;
  352.   if (old == src && old != &_nilBitStrRep) return old; 
  353.   if (old == &_nilBitStrRep) old = 0;
  354.   if (src == &_nilBitStrRep) src = 0;
  355.   if (src == 0)
  356.   {
  357.     if (old == 0)
  358.       rep = BSnew(0);
  359.     else
  360.       rep = old;
  361.     rep->len = 0;
  362.   }
  363.   else 
  364.   {
  365.     int newlen = src->len;
  366.     int news = BitStr_len(newlen);
  367.     if (old == 0 || news  > old->sz)
  368.     {
  369.       rep = BSnew(newlen);
  370.       if (old != 0) delete old;
  371.     }
  372.     else
  373.       rep = old;
  374.     
  375.     bcopy(src->s, rep->s, news * sizeof(short));
  376.     rep->len = newlen;
  377.   }
  378.   check_last(rep);
  379.   return rep;
  380. }
  381.  
  382.  
  383. int operator == (const BitString& x, const BitString& y)
  384. {
  385.   return x.rep->len == y.rep->len && 
  386.     bcmp((void*)x.rep->s, (void*)y.rep->s, 
  387.          BitStr_len(x.rep->len) * sizeof(short)) == 0;
  388. }
  389.  
  390. int operator <= (const BitString& x, const BitString& y)
  391. {
  392.   unsigned int  xl = x.rep->len;
  393.   unsigned int  yl = y.rep->len;
  394.   if (xl > yl)
  395.     return 0;
  396.  
  397.   const unsigned short* xs = x.rep->s;
  398.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  399.   const unsigned short* ys = y.rep->s;
  400.  
  401.   while (xs < topx)
  402.   {
  403.     unsigned short a = *xs++;
  404.     unsigned short b = *ys++;
  405.     if ((a | b) != b)
  406.       return 0;
  407.   }
  408.   return 1;
  409. }
  410.  
  411. int operator < (const BitString& x, const BitString& y)
  412. {
  413.   unsigned short xl = x.rep->len;
  414.   unsigned short yl = y.rep->len;
  415.   if (xl > yl)
  416.     return 0;
  417.  
  418.   const unsigned short* xs = x.rep->s;
  419.   const unsigned short* ys = y.rep->s;
  420.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  421.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  422.   int one_diff = 0;
  423.   while (xs < topx)
  424.   {
  425.     unsigned short a = *xs++;
  426.     unsigned short b = *ys++;
  427.     unsigned short c = a | b;
  428.     if (c != b)
  429.       return 0;
  430.     else if (c != a)
  431.       one_diff = 1;
  432.   }
  433.   if (one_diff)
  434.     return 1;
  435.   else
  436.   {
  437.     while (ys < topy)
  438.       if (*ys++ != 0)
  439.         return 1;
  440.     return 0;
  441.   }
  442. }
  443.  
  444. int lcompare(const BitString& x, const BitString& y)
  445. {
  446.   unsigned int  xl = x.rep->len;
  447.   unsigned int  yl = y.rep->len;
  448.  
  449.   const unsigned short* xs = x.rep->s;
  450.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  451.   const unsigned short* ys = y.rep->s;
  452.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  453.  
  454.   while (xs < topx && ys < topy)
  455.   {
  456.     unsigned short a = *xs++;
  457.     unsigned short b = *ys++;
  458.     if (a != b)
  459.     {
  460.       unsigned short mask = 1;
  461.       for (;;)
  462.       {
  463.         unsigned short abit = (a & mask) != 0;
  464.         unsigned short bbit = (b & mask) != 0;
  465.         int diff = abit - bbit;
  466.         if (diff != 0)
  467.           return diff;
  468.         else
  469.           mask <<= 1;
  470.       }
  471.     }
  472.   }
  473.   return xl - yl;
  474. }
  475.  
  476. int BitString::count(unsigned int b) const
  477. {
  478.   check_last(rep);
  479.   int xwds = BitStr_len(rep->len);
  480.   int xlast = BitStr_pos(rep->len);
  481.   int l = 0;
  482.   const unsigned short* s = rep->s;
  483.   const unsigned short* tops = &(s[xwds - 1]);
  484.   unsigned short a;
  485.   int i;
  486.   if (b != 0)
  487.   {
  488.     while (s < tops)
  489.     {
  490.       a = *s++;
  491.       for (i = 0; i < BITSTRBITS && a != 0; ++i)
  492.       {
  493.         if (a & 1)
  494.           ++l;
  495.         a >>= 1;
  496.       }
  497.     }
  498.     a = *s;
  499.     for (i = 0; i < xlast && a != 0; ++i)
  500.     {
  501.       if (a & 1)
  502.         ++l;
  503.       a >>= 1;
  504.     }
  505.   }
  506.   else
  507.   {
  508.     unsigned short maxbit = 1 << (BITSTRBITS - 1);
  509.     while (s < tops)
  510.     {
  511.       a = *s++;
  512.       for (i = 0; i < BITSTRBITS; ++i)
  513.       {
  514.         if ((a & maxbit) == 0)
  515.           ++l;
  516.         a <<= 1;
  517.       }
  518.     }
  519.     maxbit = 1 << (xlast - 1);
  520.     a = *s;
  521.     for (i = 0; i < xlast; ++i)
  522.     {
  523.       if ((a & maxbit) == 0)
  524.         ++l;
  525.       a <<= 1;
  526.     }
  527.   }
  528.   return l;
  529. }
  530.  
  531.  
  532. BitStrRep* cmpl(const BitStrRep* src, BitStrRep* r)
  533. {
  534.   r = BStr_copy(r, src);
  535.   unsigned short* rs = r->s;
  536.   unsigned short* topr = &(rs[BitStr_len(r->len)]);
  537.   while (rs < topr)
  538.   {
  539.     unsigned short cmp = ~(*rs);
  540.     *rs++ = cmp;
  541.   }
  542.   check_last(r);
  543.   return r;
  544. }
  545.  
  546.  
  547. BitStrRep* and(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  548. {
  549.   int xrsame = x == r;
  550.   int yrsame = y == r;
  551.  
  552.   unsigned int  xl = x->len;
  553.   unsigned int  yl = y->len;
  554.   unsigned int  rl = (xl <= yl)? xl : yl;
  555.  
  556.   r = BStr_resize(r, rl);
  557.  
  558.   unsigned short* rs = r->s;
  559.   unsigned short* topr = &(rs[BitStr_len(rl)]);
  560.   const unsigned short* xs = (xrsame)? rs : x->s;
  561.   const unsigned short* ys = (yrsame)? rs : y->s;
  562.  
  563.   while (rs < topr) *rs++ = *xs++ & *ys++;
  564.   check_last(r);
  565.   return r;
  566. }
  567.  
  568. BitStrRep* or(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  569. {
  570.   unsigned int  xl = x->len;
  571.   unsigned int  yl = y->len;
  572.   unsigned int  rl = (xl >= yl)? xl : yl;
  573.   int xrsame = x == r;
  574.   int yrsame = y == r;
  575.  
  576.   r = BStr_resize(r, rl);
  577.  
  578.   unsigned short* rs = r->s;
  579.   const unsigned short* xs = (xrsame)? rs : x->s;
  580.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  581.   const unsigned short* ys = (yrsame)? rs : y->s;
  582.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  583.  
  584.   if (xl <= yl)
  585.   {
  586.     while (xs < topx) *rs++ = *xs++ | *ys++;
  587.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  588.   }
  589.   else
  590.   {
  591.     while (ys < topy) *rs++ = *xs++ | *ys++;
  592.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  593.   }
  594.   check_last(r);
  595.   return r;
  596. }
  597.  
  598.  
  599. BitStrRep* xor(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  600. {
  601.   unsigned int  xl = x->len;
  602.   unsigned int  yl = y->len;
  603.   unsigned int  rl = (xl >= yl)? xl : yl;
  604.   int xrsame = x == r;
  605.   int yrsame = y == r;
  606.  
  607.   r = BStr_resize(r, rl);
  608.  
  609.   unsigned short* rs = r->s;
  610.   const unsigned short* xs = (xrsame)? rs : x->s;
  611.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  612.   const unsigned short* ys = (yrsame)? rs : y->s;
  613.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  614.  
  615.   if (xl <= yl)
  616.   {
  617.     while (xs < topx) *rs++ = *xs++ ^ *ys++;
  618.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  619.   }
  620.   else
  621.   {
  622.     while (ys < topy) *rs++ = *xs++ ^ *ys++;
  623.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  624.   }
  625.   check_last(r);
  626.   return r;
  627. }
  628.  
  629.  
  630. BitStrRep* diff(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  631. {
  632.   unsigned int  xl = x->len;
  633.   unsigned int  yl = y->len;
  634.   int xrsame = x == y;
  635.   int yrsame = y == r;
  636.  
  637.   r = BStr_resize(r, xl);
  638.  
  639.   unsigned short* rs = r->s;
  640.   const unsigned short* xs = (xrsame)? rs : x->s;
  641.   const unsigned short* topx = &(xs[BitStr_len(xl)]);
  642.   const unsigned short* ys = (yrsame)? rs : y->s;
  643.   const unsigned short* topy = &(ys[BitStr_len(yl)]);
  644.  
  645.   if (xl <= yl)
  646.   {
  647.     while (xs < topx) *rs++ = *xs++ & ~(*ys++);
  648.   }
  649.   else
  650.   {
  651.     while (ys < topy) *rs++ = *xs++ & ~(*ys++);
  652.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  653.   }
  654.   check_last(r);
  655.   return r;
  656. }
  657.  
  658.  
  659. BitStrRep* cat(const BitStrRep* x, const BitStrRep* y, BitStrRep* r)
  660. {
  661.   unsigned int  xl = x->len;
  662.   unsigned int  yl = y->len;
  663.   unsigned int  rl = xl + yl;
  664.   int xrsame = x == r;
  665.   int yrsame = y == r;
  666.  
  667.   if (yrsame)
  668.   {
  669.     if (xrsame)
  670.     {
  671.       r = BStr_resize(r, rl);
  672.       bit_transfer(r->s, 0, yl, r->s, xl);
  673.     }
  674.     else
  675.     {
  676.       BitStrRep* tmp = BStr_copy(0, y);
  677.       r = BStr_resize(r, rl);
  678.       bit_copy(x->s, r->s, xl);
  679.       bit_transfer(tmp->s, 0, yl, r->s, xl);
  680.       delete tmp;
  681.     }
  682.   }
  683.   else
  684.   {
  685.     r = BStr_resize(r, rl);
  686.     if (!xrsame) bit_copy(x->s, r->s, xl);
  687.     bit_transfer(y->s, 0, yl, r->s, xl);
  688.   }
  689.   check_last(r);
  690.   return r;
  691. }
  692.  
  693. BitStrRep* cat(const BitStrRep* x, unsigned int bit, BitStrRep* r)
  694. {
  695.   unsigned int  xl = x->len;
  696.   int xrsame = x == r;
  697.   r = BStr_resize(r, xl+1);
  698.   if (!xrsame) bit_copy(x->s, r->s, xl);
  699.   if (bit)
  700.     r->s[BitStr_index(xl)] |= (1 << (BitStr_pos(xl)));
  701.   else
  702.     r->s[BitStr_index(xl)] &= ~(1 << (BitStr_pos(xl)));
  703.   check_last(r);
  704.   return r;
  705. }
  706.  
  707. BitStrRep* lshift(const BitStrRep* x, int s, BitStrRep* r)
  708. {
  709.   int xrsame = x == r;
  710.   int  xl = x->len;
  711.   int  rl = xl + s;
  712.   if (s == 0)
  713.     r = BStr_copy(r, x);
  714.   else if (rl <= 0)
  715.   {
  716.     r = BStr_resize(r, 0);
  717.     r->len = 0;
  718.     r->s[0] = 0;
  719.   }
  720.   else if (s > 0)
  721.   {
  722.     r = BStr_resize(r, rl);
  723.     const unsigned short* xs = (xrsame)? r->s : x->s;
  724.     bit_transfer(xs, 0, xl, r->s, s);
  725.     bit_clear(r->s, s);
  726.   }
  727.   else if (xrsame)
  728.   {
  729.     r = BStr_resize(r, xl);
  730.     r->len = rl;
  731.     bit_transfer(r->s, -s, xl, r->s, 0);
  732.   }
  733.   else
  734.   {
  735.     r = BStr_resize(r, rl);
  736.     bit_transfer(x->s, -s, xl, r->s, 0);
  737.   }
  738.   check_last(r);
  739.   return r;
  740. }
  741.  
  742.  
  743. void BitString::set(int p)
  744. {
  745.   if (p < 0) error("Illegal bit index");
  746.   if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  747.   rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
  748. }
  749.  
  750. void BitString::assign(int p, unsigned int bit)
  751. {
  752.   if (p < 0) error("Illegal bit index");
  753.   if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  754.   if (bit)
  755.     rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
  756.   else
  757.     rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p)));
  758. }
  759.  
  760. void BitString::clear(int p)
  761. {
  762.   if (p < 0) error("Illegal bit index");
  763.   if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  764.   rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p)));
  765. }
  766.  
  767. void BitString::clear()
  768. {
  769.   if (rep == &_nilBitStrRep) return;
  770.   bit_clear(rep->s, rep->len);
  771. }
  772.  
  773. void BitString::set()
  774. {
  775.   if (rep == &_nilBitStrRep) return;
  776.   unsigned short* s = rep->s;
  777.   unsigned short* tops = &(s[BitStr_len(rep->len)]);
  778.   while (s < tops) *s++ = ONES;
  779.   check_last(rep);
  780. }
  781.  
  782. void BitString::invert(int p)
  783. {
  784.   if (p < 0) error("Illegal bit index");
  785.   if ((unsigned)(p) >= rep->len) rep = BStr_resize(rep, p + 1);
  786.   rep->s[BitStr_index(p)] ^= (1 << (BitStr_pos(p)));
  787. }
  788.  
  789.  
  790.  
  791. void BitString::set(int from, int to)
  792. {
  793.   if (from < 0 || from > to) error("Illegal bit index");
  794.   if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  795.  
  796.   int ind1 = BitStr_index(from);
  797.   int pos1 = BitStr_pos(from);
  798.   int ind2 = BitStr_index(to);
  799.   int pos2 = BitStr_pos(to);
  800.   unsigned short* s = &(rep->s[ind1]);
  801.   unsigned short m1 = lmask(pos1);
  802.   unsigned short m2 = rmask(pos2);
  803.   if (ind2 == ind1)
  804.     *s |= m1 & m2;
  805.   else
  806.   {
  807.     *s++ |= m1;
  808.     unsigned short* top = &(rep->s[ind2]);
  809.     *top |= m2;
  810.     while (s < top)
  811.       *s++ = ONES;
  812.   }
  813. }
  814.  
  815. void BitString::clear(int from, int to)
  816. {
  817.   if (from < 0 || from > to) error("Illegal bit index");
  818.   if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  819.  
  820.   int ind1 = BitStr_index(from);
  821.   int pos1 = BitStr_pos(from);
  822.   int ind2 = BitStr_index(to);
  823.   int pos2 = BitStr_pos(to);
  824.   unsigned short* s = &(rep->s[ind1]);
  825.   unsigned short m1 = lmask(pos1);
  826.   unsigned short m2 = rmask(pos2);
  827.   if (ind2 == ind1)
  828.     *s &= ~(m1 & m2);
  829.   else
  830.   {
  831.     *s++ &= ~m1;
  832.     unsigned short* top = &(rep->s[ind2]);
  833.     *top &= ~m2;
  834.     while (s < top)
  835.       *s++ = 0;
  836.   }
  837. }
  838.  
  839. void BitString::invert(int from, int to)
  840. {
  841.   if (from < 0 || from > to) error("Illegal bit index");
  842.   if ((unsigned)(to) >= rep->len) rep = BStr_resize(rep, to+1);
  843.  
  844.   int ind1 = BitStr_index(from);
  845.   int pos1 = BitStr_pos(from);
  846.   int ind2 = BitStr_index(to);
  847.   int pos2 = BitStr_pos(to);
  848.   unsigned short* s = &(rep->s[ind1]);
  849.   unsigned short m1 = lmask(pos1);
  850.   unsigned short m2 = rmask(pos2);
  851.   if (ind2 == ind1)
  852.     *s ^= m1 & m2;
  853.   else
  854.   {
  855.     *s++ ^= m1;
  856.     unsigned short* top = &(rep->s[ind2]);
  857.     *top ^= m2;
  858.     while (s < top)
  859.     {
  860.       unsigned short cmp = ~(*s);
  861.       *s++ = cmp;
  862.     }
  863.   }
  864. }
  865.  
  866.  
  867. int BitString::test(int from, int to) const
  868. {
  869.   if (from < 0 || from > to || (unsigned)(from) >= rep->len) return 0;
  870.   
  871.   int ind1 = BitStr_index(from);
  872.   int pos1 = BitStr_pos(from);
  873.   int ind2 = BitStr_index(to);
  874.   int pos2 = BitStr_pos(to);
  875.   
  876.   if ((unsigned)(to) >= rep->len)
  877.   {
  878.     ind2 = BitStr_index(rep->len - 1);
  879.     pos2 = BitStr_pos(rep->len - 1);
  880.   }
  881.   
  882.   const unsigned short* s = &(rep->s[ind1]);
  883.   unsigned short m1 = lmask(pos1);
  884.   unsigned short m2 = rmask(pos2);
  885.   
  886.   if (ind2 == ind1)
  887.     return (*s & m1 & m2) != 0;
  888.   else
  889.   {
  890.     if (*s++ & m1)
  891.       return 1;
  892.     unsigned short* top = &(rep->s[ind2]);
  893.     if (*top & m2)
  894.       return 1;
  895.     while (s < top)
  896.       if (*s++ != 0) 
  897.         return 1;
  898.     return 0;
  899.   }
  900. }
  901.  
  902. int BitString::next(int p, unsigned int b) const
  903. {
  904.   if ((unsigned)(++p) >= rep->len)
  905.     return -1;
  906.  
  907.   int ind = BitStr_index(p);
  908.   int pos = BitStr_pos(p);
  909.   int l = BitStr_len(rep->len);
  910.  
  911.   int j = ind;
  912.   const unsigned short* s = rep->s;
  913.   unsigned short a = s[j] >> pos;
  914.   int i = pos;
  915.  
  916.   if (b != 0)
  917.   {
  918.     for (; i < BITSTRBITS && a != 0; ++i)
  919.     {
  920.       if (a & 1)
  921.         return j * BITSTRBITS + i;
  922.       a >>= 1;
  923.     }
  924.     for (++j; j < l; ++j)
  925.     {
  926.       a = s[j];
  927.       for (i = 0; i < BITSTRBITS && a != 0; ++i)
  928.       {
  929.         if (a & 1)
  930.           return j * BITSTRBITS + i;
  931.         a >>= 1;
  932.       }
  933.     }
  934.     return -1;
  935.   }
  936.   else
  937.   {
  938.     int last = BitStr_pos(rep->len);
  939.     if (j == l - 1)
  940.     {
  941.       for (; i < last; ++i)
  942.       {
  943.         if ((a & 1) == 0)
  944.           return j * BITSTRBITS + i;
  945.         a >>= 1;
  946.       }
  947.       return -1;
  948.     }
  949.  
  950.     for (; i < BITSTRBITS; ++i)
  951.     {
  952.       if ((a & 1) == 0)
  953.         return j * BITSTRBITS + i;
  954.       a >>= 1;
  955.     }
  956.     for (++j; j < l - 1; ++j)
  957.     {
  958.       a = s[j];
  959.       if (a != ONES)
  960.       {
  961.         for (i = 0; i < BITSTRBITS; ++i)
  962.         {
  963.           if ((a & 1) == 0)
  964.             return j * BITSTRBITS + i;
  965.           a >>= 1;
  966.         }
  967.       }
  968.     }
  969.     a = s[j];
  970.     for (i = 0; i < last; ++i)
  971.     {
  972.       if ((a & 1) == 0)
  973.         return j * BITSTRBITS + i;
  974.       a >>= 1;
  975.     }
  976.     return -1;
  977.   }
  978. }
  979.  
  980. int BitString::previous(int p, unsigned int b) const
  981. {
  982.   if (--p < 0)
  983.     return -1;
  984.  
  985.   int ind = BitStr_index(p);
  986.   int pos = BitStr_pos(p);
  987.  
  988.   const unsigned short* s = rep->s;
  989.  
  990.   if ((unsigned)(p) >= rep->len)
  991.   {
  992.     ind = BitStr_index(rep->len - 1);
  993.     pos = BitStr_pos(rep->len - 1);
  994.   }
  995.  
  996.   int j = ind;
  997.   unsigned short a = s[j];
  998.  
  999.   int i = pos;
  1000.   unsigned short maxbit = 1 << pos;
  1001.  
  1002.   if (b != 0)
  1003.   {
  1004.     for (; i >= 0 && a != 0; --i)
  1005.     {
  1006.       if (a & maxbit)
  1007.         return j * BITSTRBITS + i;
  1008.       a <<= 1;
  1009.     }
  1010.     maxbit = 1 << (BITSTRBITS - 1);
  1011.     for (--j; j >= 0; --j)
  1012.     {
  1013.       a = s[j];
  1014.       for (i = BITSTRBITS - 1; i >= 0 && a != 0; --i)
  1015.       {
  1016.         if (a & maxbit)
  1017.           return j * BITSTRBITS + i;
  1018.         a <<= 1;
  1019.       }
  1020.     }
  1021.     return -1;
  1022.   }
  1023.   else
  1024.   {
  1025.     if (a != ONES)
  1026.     {
  1027.       for (; i >= 0; --i)
  1028.       {
  1029.         if ((a & maxbit) == 0)
  1030.           return j * BITSTRBITS + i;
  1031.         a <<= 1;
  1032.       }
  1033.     }
  1034.     maxbit = 1 << (BITSTRBITS - 1);
  1035.     for (--j; j >= 0; --j)
  1036.     {
  1037.       a = s[j];
  1038.       if (a != ONES)
  1039.       {
  1040.         for (i = BITSTRBITS - 1; i >= 0; --i)
  1041.         {
  1042.           if ((a & maxbit) == 0)
  1043.             return j * BITSTRBITS + i;
  1044.           a <<= 1;
  1045.         }
  1046.       }
  1047.     }
  1048.     return -1;
  1049.   }
  1050. }
  1051.  
  1052.  
  1053. int BitString::search(int startx, int lengthx, 
  1054.                       const unsigned short* ys, int starty, int lengthy) const
  1055. {
  1056.   const unsigned short* xs = rep->s;
  1057.   int ylen = lengthy - starty;
  1058.   int righty = lengthy - 1;
  1059.   int rev = startx < 0;
  1060.   if (rev)
  1061.   {
  1062.     int leftx = 0;
  1063.     int rightx = lengthx + startx;
  1064.     startx = rightx - ylen + 1;
  1065.     if (ylen == 0) return startx;
  1066.     if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
  1067.     
  1068.     int xind = BitStr_index(startx);
  1069.     int xpos = BitStr_pos(startx);
  1070.     int yind = BitStr_index(starty);
  1071.     int ypos = BitStr_pos(starty);
  1072.     
  1073.     int rightxind = BitStr_index(rightx);
  1074.  
  1075.     unsigned short x = borrow_hi(xs, xind, rightxind, xpos);
  1076.   
  1077.     int rightyind = BitStr_index(righty);
  1078.     int rightypos = BitStr_pos(righty);
  1079.     unsigned short y = borrow_hi(ys, yind, rightyind, ypos);
  1080.     unsigned short ymask;
  1081.     if (yind == rightyind)
  1082.       ymask = rmask(rightypos);
  1083.     else if (yind+1 == rightyind)
  1084.       ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
  1085.     else
  1086.       ymask = ONES;
  1087.     
  1088.     int p = startx;
  1089.     for (;;)
  1090.     {
  1091.       if ((x & ymask) == y)
  1092.       {
  1093.         int xi = xind;
  1094.         int yi = yind;
  1095.         for (;;)
  1096.         {
  1097.           if (++yi > rightyind || ++xi > rightxind)
  1098.             return p;
  1099.           unsigned short tx = borrow_hi(xs, xi, rightxind, xpos);
  1100.           unsigned short ty = borrow_hi(ys, yi, rightyind, ypos);
  1101.           if (yi == rightyind)
  1102.             tx &= rmask(rightypos);
  1103.           else if (yi+1 == rightyind)
  1104.             tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1105.           if (tx != ty)
  1106.             break;
  1107.         }
  1108.       }
  1109.       if (--p < leftx)
  1110.         return -1;
  1111.       if (--xpos < 0)
  1112.       {
  1113.         xpos = BITSTRBITS - 1;
  1114.         --xind;
  1115.       }
  1116.       x = borrow_hi(xs, xind, rightxind, xpos);
  1117.     }
  1118.   }
  1119.   else
  1120.   {
  1121.  
  1122.     int rightx = lengthx - 1;
  1123.     if (ylen == 0) return startx;
  1124.     if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
  1125.     
  1126.     int xind = BitStr_index(startx);
  1127.     int xpos = BitStr_pos(startx);
  1128.     int yind = BitStr_index(starty);
  1129.     int ypos = BitStr_pos(starty);
  1130.  
  1131.     int rightxind = BitStr_index(rightx);
  1132.  
  1133.     unsigned short x = borrow_hi(xs, xind, rightxind, xpos);
  1134.     unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  1135.   
  1136.     int rightyind = BitStr_index(righty);
  1137.     int rightypos = BitStr_pos(righty);
  1138.     unsigned short y = borrow_hi(ys, yind, rightyind, ypos);
  1139.     unsigned short ymask;
  1140.     if (yind == rightyind)
  1141.       ymask = rmask(rightypos);
  1142.     else if (yind+1 == rightyind)
  1143.       ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
  1144.     else
  1145.       ymask = ONES;
  1146.   
  1147.     int p = startx;
  1148.     for (;;)
  1149.     {
  1150.       if ((x & ymask) == y)
  1151.       {
  1152.         int xi = xind;
  1153.         int yi = yind;
  1154.         for (;;)
  1155.         {
  1156.           if (++yi > rightyind || ++xi > rightxind)
  1157.             return p;
  1158.           unsigned short tx = borrow_hi(xs, xi, rightxind, xpos);
  1159.           unsigned short ty = borrow_hi(ys, yi, rightyind, ypos);
  1160.           if (yi == rightyind)
  1161.             tx &= rmask(rightypos);
  1162.           else if (yi+1 == rightyind)
  1163.             tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1164.           if (tx != ty)
  1165.             break;
  1166.         }
  1167.       }
  1168.       if (++p > rightx)
  1169.         return -1;
  1170.       if (++xpos == BITSTRBITS)
  1171.       {
  1172.         xpos = 0;
  1173.         x = xs[++xind];
  1174.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1175.       }
  1176.       else
  1177.       {
  1178.         x >>= 1;
  1179.         if (nextx & 1)
  1180.           x |= MAXBIT;
  1181.         nextx >>= 1;
  1182.       }
  1183.     }
  1184.   }
  1185. }
  1186.  
  1187.  
  1188. int BitPattern::search(const unsigned short* xs, int startx, int lengthx) const
  1189. {
  1190.   const unsigned short* ys = pattern.rep->s;
  1191.   const unsigned short* ms = mask.rep->s;
  1192.   int righty = pattern.rep->len - 1;
  1193.   int rightm = mask.rep->len - 1;
  1194.  
  1195.   int rev = startx < 0;
  1196.   if (rev)
  1197.   {
  1198.     int leftx = 0;
  1199.     int rightx = lengthx + startx;
  1200.     startx = rightx - righty;
  1201.  
  1202.     if (righty < 0) return startx;
  1203.     if (startx < 0 || startx >= lengthx) return -1;
  1204.   
  1205.     int xind = BitStr_index(startx);
  1206.     int xpos = BitStr_pos(startx);
  1207.     
  1208.     int rightxind = BitStr_index(rightx);
  1209.  
  1210.     int rightmind = BitStr_index(rightm);
  1211.     int rightyind = BitStr_index(righty);
  1212.     
  1213.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1214.     unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0);
  1215.     unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  1216.     
  1217.     int p = startx;
  1218.     for (;;)
  1219.     {
  1220.       if ((x & m) == y)
  1221.       {
  1222.         int xi = xind;
  1223.         int yi = 0;
  1224.         for (;;)
  1225.         {
  1226.           if (++yi > rightyind || ++xi > rightxind)
  1227.             return p;
  1228.           unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0);
  1229.           unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0);
  1230.           unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  1231.           if ((tx & tm) != (ty & tm))
  1232.             break;
  1233.         }
  1234.       }
  1235.       if (--p < leftx)
  1236.         return -1;
  1237.       if (--xpos < 0)
  1238.       {
  1239.         xpos = BITSTRBITS - 1;
  1240.         --xind;
  1241.       }
  1242.       x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1243.     }
  1244.   }
  1245.   else
  1246.   {
  1247.  
  1248.     int rightx = lengthx - 1;
  1249.  
  1250.     if (righty < 0) return startx;
  1251.     if (startx < 0 || startx >= lengthx) return -1;
  1252.     
  1253.     int xind = BitStr_index(startx);
  1254.     int xpos = BitStr_pos(startx);
  1255.     
  1256.     int rightxind = BitStr_index(rightx);
  1257.  
  1258.     int rightmind = BitStr_index(rightm);
  1259.     int rightyind = BitStr_index(righty);
  1260.     
  1261.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1262.     unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0);
  1263.     unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  1264.  
  1265.     unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  1266.     
  1267.     int p = startx;
  1268.     for (;;)
  1269.     {
  1270.       if ((x & m) == y)
  1271.       {
  1272.         int xi = xind;
  1273.         int yi = 0;
  1274.         for (;;)
  1275.         {
  1276.           if (++yi > rightyind || ++xi > rightxind)
  1277.             return p;
  1278.           unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0);
  1279.           unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0);
  1280.           unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  1281.           if ((tx & tm) != (ty & tm))
  1282.             break;
  1283.         }
  1284.       }
  1285.       if (++p > rightx)
  1286.         return -1;
  1287.       if (++xpos == BITSTRBITS)
  1288.       {
  1289.         xpos = 0;
  1290.         x = xs[++xind];
  1291.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1292.       }
  1293.       else
  1294.       {
  1295.         x >>= 1;
  1296.         if (nextx & 1)
  1297.           x |= MAXBIT;
  1298.         nextx >>= 1;
  1299.       }
  1300.     }
  1301.   }
  1302. }
  1303.  
  1304. int BitString::match(int startx, int lengthx, int exact, 
  1305.                      const unsigned short* ys, int starty, int yl) const
  1306. {
  1307.   const unsigned short* xs = rep->s;
  1308.   int ylen = yl - starty;
  1309.   int righty = yl - 1;
  1310.  
  1311.   int rightx;
  1312.   int rev = startx < 0;
  1313.   if (rev)
  1314.   {
  1315.     rightx = lengthx + startx;
  1316.     startx = rightx - ylen + 1;
  1317.     if (exact && startx != 0)
  1318.       return 0;
  1319.   }
  1320.   else
  1321.   {
  1322.     rightx = lengthx - 1;
  1323.     if (exact && rightx - startx != righty)
  1324.       return 0;
  1325.   }
  1326.  
  1327.   if (ylen == 0) return 1;
  1328.   if (righty < 0 || startx < 0 || startx >= lengthx) return 0;
  1329.   
  1330.   int xi   = BitStr_index(startx);
  1331.   int xpos = BitStr_pos(startx);
  1332.   int yi   = BitStr_index(starty);
  1333.   int ypos = BitStr_pos(starty);
  1334.  
  1335.   int rightxind = BitStr_index(rightx);
  1336.   int rightyind = BitStr_index(righty);
  1337.   int rightypos = BitStr_pos(righty);
  1338.  
  1339.   for (;;)
  1340.   {
  1341.     unsigned short x = borrow_hi(xs, xi, rightxind, xpos);
  1342.     unsigned short y = borrow_hi(ys, yi, rightyind, ypos);
  1343.     if (yi == rightyind)
  1344.       x &= rmask(rightypos);
  1345.     else if (yi+1 == rightyind)
  1346.       x &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1347.     if (x != y)
  1348.       return 0;
  1349.     else if (++yi > rightyind || ++xi > rightxind)
  1350.       return 1;
  1351.   }
  1352. }
  1353.  
  1354. int BitPattern::match(const unsigned short* xs, int startx, 
  1355.                       int lengthx, int exact) const
  1356. {
  1357.   const unsigned short* ys = pattern.rep->s;
  1358.   int righty = pattern.rep->len - 1;
  1359.   unsigned short* ms = mask.rep->s;
  1360.   int rightm = mask.rep->len - 1;
  1361.  
  1362.   int rightx;
  1363.   int rev = startx < 0;
  1364.   if (rev)
  1365.   {
  1366.     rightx = lengthx + startx;
  1367.     startx = rightx - righty;
  1368.     if (exact && startx != 0)
  1369.       return 0;
  1370.   }
  1371.   else
  1372.   {
  1373.     rightx = lengthx - 1;
  1374.     if (exact && rightx - startx != righty)
  1375.       return 0;
  1376.   }
  1377.  
  1378.   if (righty < 0) return 1;
  1379.   if (startx < 0 || startx >= lengthx) return 0;
  1380.   
  1381.   int xind = BitStr_index(startx);
  1382.   int xpos = BitStr_pos(startx);
  1383.   int yind = 0;
  1384.  
  1385.   int rightxind = BitStr_index(rightx);
  1386.   int rightyind = BitStr_index(righty);
  1387.   int rightmind = BitStr_index(rightm);
  1388.  
  1389.   for(;;)
  1390.   {
  1391.     unsigned short m = safe_borrow_hi(ms, yind, rightmind, 0);
  1392.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos) & m;
  1393.     unsigned short y = safe_borrow_hi(ys, yind, rightyind, 0) & m;
  1394.     if (x != y)
  1395.       return 0;
  1396.     else if (++yind > rightyind || ++xind > rightxind)
  1397.       return 1;
  1398.   }
  1399. }
  1400.  
  1401. void BitSubString::operator = (const BitString& y)
  1402. {
  1403.   if (&S == &_nil_BitString) return;
  1404.   BitStrRep* targ = S.rep;
  1405.  
  1406.   unsigned int ylen = y.rep->len;
  1407.   int sl = targ->len - len + ylen;
  1408.  
  1409.   if (y.rep == targ || ylen > len)
  1410.   {
  1411.     BitStrRep* oldtarg = targ;
  1412.     targ = BStr_alloc(0, 0, 0, 0, sl);
  1413.     bit_transfer(oldtarg->s, 0, pos, targ->s, 0);
  1414.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1415.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + ylen);
  1416.     delete oldtarg;
  1417.   }
  1418.   else if (len == ylen)
  1419.     bit_transfer(y.rep->s, 0, len, targ->s, pos);
  1420.   else if (ylen < len)
  1421.   {
  1422.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1423.     bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + ylen);
  1424.     targ->len = sl;
  1425.   }
  1426.   check_last(targ);
  1427.   S.rep = targ;
  1428. }
  1429.  
  1430. void BitSubString::operator = (const BitSubString& y)
  1431. {
  1432.   if (&S == &_nil_BitString) return;
  1433.   BitStrRep* targ = S.rep;
  1434.   
  1435.   if (len == 0 || pos >= targ->len)
  1436.     return;
  1437.   
  1438.   int sl = targ->len - len + y.len;
  1439.   
  1440.   if (y.S.rep == targ || y.len > len)
  1441.   {
  1442.     BitStrRep* oldtarg = targ;
  1443.     targ = BStr_alloc(0, 0, 0, 0, sl);
  1444.     bit_copy(oldtarg->s, targ->s, pos);
  1445.     bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1446.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + y.len);
  1447.     delete oldtarg;
  1448.   }
  1449.   else if (len == y.len)
  1450.     bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1451.   else if (y.len < len)
  1452.   {
  1453.     bit_transfer(y.S.rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1454.     bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + y.len);
  1455.     targ->len = sl;
  1456.   }
  1457.   check_last(targ);
  1458.   S.rep = targ;
  1459. }
  1460.  
  1461. BitSubString BitString::at(int first, int len)
  1462. {
  1463.   return _substr(first, len);
  1464. }
  1465.  
  1466. BitSubString BitString::before(int pos)
  1467. {
  1468.   return _substr(0, pos);
  1469. }
  1470.  
  1471. BitSubString BitString::after(int pos)
  1472. {
  1473.   return _substr(pos + 1, rep->len - (pos + 1));
  1474. }
  1475.  
  1476. BitSubString BitString::at(const BitString& y, int startpos)
  1477. {
  1478.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1479.   return _substr(first,  y.rep->len);
  1480. }
  1481.  
  1482. BitSubString BitString::before(const BitString& y, int startpos)
  1483. {
  1484.   int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1485.   return _substr(0, last);
  1486. }
  1487.  
  1488. BitSubString BitString::after(const BitString& y, int startpos)
  1489. {
  1490.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1491.   if (first >= 0) first += y.rep->len;
  1492.   return _substr(first, rep->len - first);
  1493. }
  1494.  
  1495.  
  1496. BitSubString BitString::at(const BitSubString& y, int startpos)
  1497. {
  1498.   int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1499.   return _substr(first, y.len);
  1500. }
  1501.  
  1502. BitSubString BitString::before(const BitSubString& y, int startpos)
  1503. {
  1504.   int last = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1505.   return _substr(0, last);
  1506. }
  1507.  
  1508. BitSubString BitString::after(const BitSubString& y, int startpos)
  1509. {
  1510.   int first = search(startpos, rep->len, y.S.rep->s, y.pos, y.len);
  1511.   if (first >= 0) first += y.len;
  1512.   return _substr(first, rep->len - first);
  1513. }
  1514.  
  1515. BitSubString BitString::at(const BitPattern& r, int startpos)
  1516. {
  1517.   int first = r.search(rep->s, startpos, rep->len);
  1518.   return _substr(first, r.pattern.rep->len);
  1519. }
  1520.  
  1521.  
  1522. BitSubString BitString::before(const BitPattern& r, int startpos)
  1523. {
  1524.   int first = r.search(rep->s, startpos, rep->len);
  1525.   return _substr(0, first);
  1526. }
  1527.  
  1528. BitSubString BitString::after(const BitPattern& r, int startpos)
  1529. {
  1530.   int first = r.search(rep->s, startpos, rep->len);
  1531.   if (first >= 0) first += r.pattern.rep->len;
  1532.   return _substr(first, rep->len - first);
  1533. }
  1534.  
  1535. #if defined(__GNUG__) && !defined(NO_NRV)
  1536.  
  1537. BitString common_prefix(const BitString& x, const BitString& y, int startpos)
  1538.      return r
  1539. {
  1540.   unsigned int  xl = x.rep->len;
  1541.   unsigned int  yl = y.rep->len;
  1542.  
  1543.   unsigned int startx, starty;
  1544.   if (startpos < 0)
  1545.   {
  1546.     startx = xl + startpos;
  1547.     starty = yl + startpos;
  1548.   }
  1549.   else
  1550.     startx = starty = startpos;
  1551.  
  1552.   if (startx >= xl || starty >= yl)
  1553.     return;
  1554.  
  1555.   const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1556.   unsigned short a = *xs++;
  1557.   unsigned int xp = startx;
  1558.  
  1559.   const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1560.   unsigned short b = *ys++;
  1561.   unsigned int yp = starty;
  1562.  
  1563.   for(; xp < xl && yp < yl; ++xp, ++yp)
  1564.   {
  1565.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1566.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1567.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1568.       break;
  1569.     if (xbit == MAXBIT)
  1570.       a = *xs++;
  1571.     if (ybit == MAXBIT)
  1572.       b = *ys++;
  1573.   }
  1574.   r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx);
  1575. }
  1576.  
  1577.  
  1578. BitString common_suffix(const BitString& x, const BitString& y, int startpos)
  1579.      return r;
  1580. {
  1581.   unsigned int  xl = x.rep->len;
  1582.   unsigned int  yl = y.rep->len;
  1583.  
  1584.   unsigned int startx, starty;
  1585.   if (startpos < 0)
  1586.   {
  1587.     startx = xl + startpos;
  1588.     starty = yl + startpos;
  1589.   }
  1590.   else
  1591.     startx = starty = startpos;
  1592.  
  1593.   if (startx >= xl || starty >= yl)
  1594.     return;
  1595.  
  1596.   const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1597.   unsigned short a = *xs--;
  1598.   int xp = startx;
  1599.  
  1600.   const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1601.   unsigned short b = *ys--;
  1602.   int yp = starty;
  1603.  
  1604.   for(; xp >= 0 && yp >= 0; --xp, --yp)
  1605.   {
  1606.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1607.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1608.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1609.       break;
  1610.     if (xbit == 1)
  1611.       a = *xs--;
  1612.     if (ybit == 1)
  1613.       b = *ys--;
  1614.   }
  1615.   r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp);
  1616. }
  1617.  
  1618. BitString reverse(const BitString& x) return r
  1619. {
  1620.   unsigned int  yl = x.rep->len;
  1621.   BitStrRep* y = BStr_resize(0, yl);
  1622.   if (yl > 0)
  1623.   {
  1624.     const unsigned short* ls = x.rep->s;
  1625.     unsigned short lm = 1;
  1626.     unsigned short* rs = &(y->s[BitStr_index(yl - 1)]);
  1627.     unsigned short rm = 1 << (BitStr_pos(yl - 1));
  1628.     for (unsigned int  l = 0; l < yl; ++l)
  1629.     {
  1630.       if (*ls & lm)
  1631.         *rs |= rm;
  1632.       if (lm == MAXBIT)
  1633.       {
  1634.         ++ls;
  1635.         lm = 1;
  1636.       }
  1637.       else
  1638.         lm <<= 1;
  1639.       if (rm == 1)
  1640.       {
  1641.         --rs;
  1642.         rm = MAXBIT;
  1643.       }
  1644.       else
  1645.         rm >>= 1;
  1646.     }
  1647.   }
  1648.   r.rep = y;
  1649. }
  1650.  
  1651. BitString atoBitString(const char* s, char f, char t) return res
  1652. {
  1653.   int sl = strlen(s);
  1654.   BitStrRep* r = BStr_resize(0, sl);
  1655.   if (sl != 0)
  1656.   {
  1657.     unsigned int  rl = 0;
  1658.     unsigned short* rs = r->s;
  1659.     unsigned short a = 0;
  1660.     unsigned short m = 1;
  1661.     unsigned int  i = 0;
  1662.     for(;;)
  1663.     {
  1664.       char ch = s[i];
  1665.       if (ch != t && ch != f)
  1666.       {
  1667.         *rs = a;
  1668.         break;
  1669.       }
  1670.       ++rl;
  1671.       if (ch == t)
  1672.         a |= m;
  1673.       if (++i == sl)
  1674.       {
  1675.         *rs = a;
  1676.         break;
  1677.       }
  1678.       else if (i % BITSTRBITS == 0)
  1679.       {
  1680.         *rs++ = a;
  1681.         a = 0;
  1682.         m = 1;
  1683.       }
  1684.       else
  1685.         m <<= 1;
  1686.     }
  1687.     r = BStr_resize(r, rl);
  1688.   }
  1689.   res.rep = r;
  1690. }
  1691.  
  1692. BitPattern atoBitPattern(const char* s, char f,char t,char x) return r
  1693. {
  1694.   int sl = strlen(s);
  1695.   if (sl != 0)
  1696.   {
  1697.     unsigned int  rl = 0;
  1698.     r.pattern.rep = BStr_resize(r.pattern.rep, sl);
  1699.     r.mask.rep = BStr_resize(r.mask.rep, sl);
  1700.     unsigned short* rs = r.pattern.rep->s;
  1701.     unsigned short* ms = r.mask.rep->s;
  1702.     unsigned short a = 0;
  1703.     unsigned short b = 0;
  1704.     unsigned short m = 1;
  1705.     unsigned int  i = 0;
  1706.     for(;;)
  1707.     {
  1708.       char ch = s[i];
  1709.       if (ch != t && ch != f && ch != x)
  1710.       {
  1711.         *rs = a;
  1712.         *ms = b;
  1713.         break;
  1714.       }
  1715.       ++rl;
  1716.       if (ch == t)
  1717.       {
  1718.         a |= m;
  1719.         b |= m;
  1720.       }
  1721.       else if (ch == f)
  1722.       {
  1723.         b |= m;
  1724.       }
  1725.       if (++i == sl)
  1726.       {
  1727.         *rs = a;
  1728.         *ms = b;
  1729.         break;
  1730.       }
  1731.       else if (i % BITSTRBITS == 0)
  1732.       {
  1733.         *rs++ = a;
  1734.         *ms++ = b;
  1735.         a = 0;
  1736.         b = 0;
  1737.         m = 1;
  1738.       }
  1739.       else
  1740.         m <<= 1;
  1741.     }
  1742.     r.pattern.rep = BStr_resize(r.pattern.rep, rl);
  1743.     r.mask.rep = BStr_resize(r.mask.rep, rl);
  1744.   }
  1745.   return;
  1746. }
  1747.  
  1748. #else /* NO_NRV */
  1749.  
  1750. BitString common_prefix(const BitString& x, const BitString& y, int startpos)
  1751. {
  1752.   BitString r;
  1753.  
  1754.   unsigned int  xl = x.rep->len;
  1755.   unsigned int  yl = y.rep->len;
  1756.  
  1757.   int startx, starty;
  1758.   if (startpos < 0)
  1759.   {
  1760.     startx = xl + startpos;
  1761.     starty = yl + startpos;
  1762.   }
  1763.   else
  1764.     startx = starty = startpos;
  1765.  
  1766.   if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
  1767.     return r;
  1768.  
  1769.   const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1770.   unsigned short a = *xs++;
  1771.   int xp = startx;
  1772.  
  1773.   const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1774.   unsigned short b = *ys++;
  1775.   int yp = starty;
  1776.  
  1777.   for(; xp < xl && yp < yl; ++xp, ++yp)
  1778.   {
  1779.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1780.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1781.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1782.       break;
  1783.     if (xbit == MAXBIT)
  1784.       a = *xs++;
  1785.     if (ybit == MAXBIT)
  1786.       b = *ys++;
  1787.   }
  1788.   r.rep = BStr_alloc(0, x.rep->s, startx, xp, xp - startx);
  1789.   return r;
  1790. }
  1791.  
  1792.  
  1793. BitString common_suffix(const BitString& x, const BitString& y, int startpos)
  1794. {
  1795.   BitString r;
  1796.   unsigned int  xl = x.rep->len;
  1797.   unsigned int  yl = y.rep->len;
  1798.  
  1799.   int startx, starty;
  1800.   if (startpos < 0)
  1801.   {
  1802.     startx = xl + startpos;
  1803.     starty = yl + startpos;
  1804.   }
  1805.   else
  1806.     startx = starty = startpos;
  1807.  
  1808.   if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
  1809.     return r;
  1810.  
  1811.   const unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1812.   unsigned short a = *xs--;
  1813.   int xp = startx;
  1814.  
  1815.   const unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1816.   unsigned short b = *ys--;
  1817.   int yp = starty;
  1818.  
  1819.   for(; xp >= 0 && yp >= 0; --xp, --yp)
  1820.   {
  1821.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1822.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1823.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1824.       break;
  1825.     if (xbit == 1)
  1826.       a = *xs--;
  1827.     if (ybit == 1)
  1828.       b = *ys--;
  1829.   }
  1830.   r.rep = BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp);
  1831.   return r;
  1832. }
  1833.  
  1834. BitString reverse(const BitString& x)
  1835. {
  1836.   BitString r;
  1837.   unsigned int  yl = x.rep->len;
  1838.   BitStrRep* y = BStr_resize(0, yl);
  1839.   if (yl > 0)
  1840.   {
  1841.     const unsigned short* ls = x.rep->s;
  1842.     unsigned short lm = 1;
  1843.     unsigned short* rs = &(y->s[BitStr_index(yl - 1)]);
  1844.     unsigned short rm = 1 << (BitStr_pos(yl - 1));
  1845.     for (unsigned int  l = 0; l < yl; ++l)
  1846.     {
  1847.       if (*ls & lm)
  1848.         *rs |= rm;
  1849.       if (lm == MAXBIT)
  1850.       {
  1851.         ++ls;
  1852.         lm = 1;
  1853.       }
  1854.       else
  1855.         lm <<= 1;
  1856.       if (rm == 1)
  1857.       {
  1858.         --rs;
  1859.         rm = MAXBIT;
  1860.       }
  1861.       else
  1862.         rm >>= 1;
  1863.     }
  1864.   }
  1865.   r.rep = y;
  1866.   return r;
  1867. }
  1868.  
  1869. BitString atoBitString(const char* s, char f, char t)
  1870. {
  1871.   BitString res;
  1872.   int sl = strlen(s);
  1873.   BitStrRep* r = BStr_resize(0, sl);
  1874.   if (sl != 0)
  1875.   {
  1876.     unsigned int  rl = 0;
  1877.     unsigned short* rs = r->s;
  1878.     unsigned short a = 0;
  1879.     unsigned short m = 1;
  1880.     unsigned int  i = 0;
  1881.     for(;;)
  1882.     {
  1883.       char ch = s[i];
  1884.       if (ch != t && ch != f)
  1885.       {
  1886.         *rs = a;
  1887.         break;
  1888.       }
  1889.       ++rl;
  1890.       if (ch == t)
  1891.         a |= m;
  1892.       if (++i == sl)
  1893.       {
  1894.         *rs = a;
  1895.         break;
  1896.       }
  1897.       else if (i % BITSTRBITS == 0)
  1898.       {
  1899.         *rs++ = a;
  1900.         a = 0;
  1901.         m = 1;
  1902.       }
  1903.       else
  1904.         m <<= 1;
  1905.     }
  1906.     r = BStr_resize(r, rl);
  1907.   }
  1908.   res.rep = r;
  1909.   return res;
  1910. }
  1911.  
  1912. BitPattern atoBitPattern(const char* s, char f,char t,char x)
  1913. {
  1914.   BitPattern r;
  1915.   int sl = strlen(s);
  1916.   if (sl != 0)
  1917.   {
  1918.     unsigned int  rl = 0;
  1919.     r.pattern.rep = BStr_resize(r.pattern.rep, sl);
  1920.     r.mask.rep = BStr_resize(r.mask.rep, sl);
  1921.     unsigned short* rs = r.pattern.rep->s;
  1922.     unsigned short* ms = r.mask.rep->s;
  1923.     unsigned short a = 0;
  1924.     unsigned short b = 0;
  1925.     unsigned short m = 1;
  1926.     unsigned int  i = 0;
  1927.     for(;;)
  1928.     {
  1929.       char ch = s[i];
  1930.       if (ch != t && ch != f && ch != x)
  1931.       {
  1932.         *rs = a;
  1933.         *ms = b;
  1934.         break;
  1935.       }
  1936.       ++rl;
  1937.       if (ch == t)
  1938.       {
  1939.         a |= m;
  1940.         b |= m;
  1941.       }
  1942.       else if (ch == f)
  1943.       {
  1944.         b |= m;
  1945.       }
  1946.       if (++i == sl)
  1947.       {
  1948.         *rs = a;
  1949.         *ms = b;
  1950.         break;
  1951.       }
  1952.       else if (i % BITSTRBITS == 0)
  1953.       {
  1954.         *rs++ = a;
  1955.         *ms++ = b;
  1956.         a = 0;
  1957.         b = 0;
  1958.         m = 1;
  1959.       }
  1960.       else
  1961.         m <<= 1;
  1962.     }
  1963.     r.pattern.rep = BStr_resize(r.pattern.rep, rl);
  1964.     r.mask.rep = BStr_resize(r.mask.rep, rl);
  1965.   }
  1966.   return r;
  1967. }
  1968.  
  1969. #endif
  1970.  
  1971. extern AllocRing _libgxx_fmtq;
  1972.  
  1973. const char* BitStringtoa(const BitString& x, char f, char t)
  1974. {
  1975.   int wrksiz = x.length() + 2;
  1976.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  1977.   char* fmt = fmtbase;
  1978.   unsigned int  xl = x.rep->len;
  1979.   const unsigned short* s = x.rep->s;
  1980.   unsigned short a = 0;
  1981.  
  1982.   for (unsigned int  i = 0; i < xl; ++i)
  1983.   {
  1984.     if (i % BITSTRBITS == 0)
  1985.       a = *s++;
  1986.     *fmt++ = (a & 1)? t : f;
  1987.     a >>= 1;
  1988.   }
  1989.  
  1990.   *fmt = 0;
  1991.  
  1992.   return fmtbase;
  1993. }
  1994.  
  1995.  
  1996. ostream& operator << (ostream& s, const BitString& x)
  1997. {
  1998.   return s << BitStringtoa(x);
  1999. }
  2000.  
  2001. const char* BitPatterntoa(const BitPattern& p, char f,char t,char x)
  2002. {
  2003.   unsigned int  pl = p.pattern.rep->len;
  2004.   unsigned int  ml = p.mask.rep->len;
  2005.   unsigned int  l = (pl <= ml)? pl : ml;
  2006.  
  2007.   int wrksiz = l + 2;
  2008.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  2009.   char* fmt = fmtbase;
  2010.  
  2011.   const unsigned short* ps = p.pattern.rep->s;
  2012.   const unsigned short* ms = p.mask.rep->s;
  2013.   unsigned short a = 0;
  2014.   unsigned short m = 0;
  2015.  
  2016.   for (unsigned int  i = 0; i < l; ++i)
  2017.   {
  2018.     if (i % BITSTRBITS == 0)
  2019.     {
  2020.       a = *ps++;
  2021.       m = *ms++;
  2022.     }
  2023.     if (m & 1)
  2024.       *fmt++ =(a & 1)? t : f;
  2025.     else
  2026.       *fmt++ = x;
  2027.     a >>= 1;
  2028.     m >>= 1;
  2029.   }
  2030.  
  2031.   *fmt = 0;
  2032.   return fmtbase;
  2033. }
  2034.  
  2035.  
  2036. ostream& operator << (ostream& s, const BitPattern& x)
  2037. {
  2038.   return s << BitPatterntoa(x);
  2039. }
  2040.  
  2041.  
  2042. int BitString::OK() const
  2043. {
  2044.   int v = rep != 0;             // have a rep;
  2045.   v &= BitStr_len(rep->len) <= rep->sz; // within allocated size
  2046.   if (!v) error("invariant failure");
  2047.   return v;
  2048. }
  2049.  
  2050. int BitSubString::OK() const
  2051. {
  2052.   int v = S.OK();               // valid BitString
  2053.   v &= pos + len <= S.rep->len; // within bounds of targ
  2054.   if (!v) S.error("BitSubString invariant failure");
  2055.   return v;
  2056. }
  2057.  
  2058. int BitPattern::OK() const
  2059. {
  2060.   int v = pattern.OK() && mask.OK();
  2061.   if (!v) pattern.error("BitPattern invariant failure");
  2062.   return v;
  2063. }
  2064.  
  2065.